import org.junit.jupiter.api.Test;

import java.util.*;

/**
 * @author ZhengDp
 * @Date 2023/4/1 19:03
 */
public class 数组_链表_跳表 {
    /*
     * #problem 283 移动0
     * */
    public void moveZeroes(int[] nums) {
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        for (; j < nums.length; j++) {
            nums[j] = 0;
        }

    }

    /*
     * #problem 11 最大盛水容器
     * */
    // 1. 确定左边界 遍历确定最大右边界 ==> 会超时
    public int maxArea(int[] height) {
        int result = 0;
        for (int left = 0; left < height.length - 1; left++) {
            for (int right = left + 1; right < height.length; right++) {
                int h = Math.min(height[left], height[right]);
                result = Math.max(result, h * (right - left));
            }
        }
        return result;
    }

    // 2. 双指针，一个指向左，一个指向右，每次移动较短的板子，更新最大值
    // 在移动过程中，不断消去不可能成为最大值的状态
    public int maxArea1(int[] height) {
        int result = 0;
        int left = 0, right = height.length - 1;
        while (left < right) {
            int length = right - left;
            result = height[left] < height[right] ? Math.max(result, length * height[left++]) : Math.max(result, length * height[right--]);
        }
        return result;
    }

    /*
     * #problem 70 爬楼梯
     * */
    @Test
    void test1() {
        System.out.println(climbStairs(44));
        ;
    }

    // 1. 递归解法会超时,所以使用一个temp数组来记录中间结果值，用于加速递归的过程
    public int climbStairs(int n) {
        int[] temp = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            temp[i] = -1;
        }
        return f(n, temp);
    }

    private int f(int n, int[] temp) {
        if (n < 0) {
            return 0;
        } else if (temp[n] != -1) {
            return temp[n];
        } else if (n == 0) {
            return 1;
        }
        temp[n] = f(n - 1, temp) + f(n - 2, temp);
        return temp[n];
    }

    // 2.动态规划  f(x) = f(x-1) + f(x-2)
    // f(0) = 1 f(1) = 1 ==> 计算得到整个矩阵
    // 当 i++ , 之前的 r = f(x-1) 而之前的 f(x-1) = f(x-2)
    public int climbStairs1(int n) {
        int x_1 = 0, x_2 = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            x_2 = x_1;
            x_1 = r;
            r = x_1 + x_2;
        }
        return r;
    }

    // 3.动态规划
    public int climbStairs2(int n) {
        int[] result = new int[n + 1];
        result[0] = 1;
        if (n >= 1) {
            result[1] = 1;
        }
        for (int i = 2; i <= n; i++) {
            result[i] = result[i - 1] + result[i - 2];
        }
        return result[n];
    }

    /*
     * #problem 15 三数之和
     * */

    // 1. 双指针
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        // 升序排序
        Arrays.sort(nums);
        int length = nums.length;
        for (int first = 0; first < length; ++first) {
            // 去重
            if (first > 0 && nums[first] == nums[first - 1]) {
                continue;
            }
            int a = nums[first];
            int target = -a;
            int third = length - 1;
            for (int second = first + 1; second < length; ++second) {
                // 确定b
                if (second > first + 1 && nums[second] == nums[second - 1]) {
                    continue;
                }
                int b = nums[second];
                // 确定third
                while (second < third && b + nums[third] > target) {
                    third--;
                }
                // 当 second == third ==> 此时 b + c > -a ==> 而且随着b++ b' > b ==> a + b +c != 0
                if (second == third) {
                    break;
                }
                int c = nums[third];
                if (b + c == target) {
                    List<Integer> temp = new ArrayList<>();
                    temp.add(a);
                    temp.add(b);
                    temp.add(c);
                    result.add(temp);
                }
            }
        }
        return result;
    }

    // 2.双指针 （不同写法）
    public List<List<Integer>> threeSum1(int[] nums) {
        List<List<Integer>> result = new ArrayList();
        Arrays.sort(nums);
        int length = nums.length;
        for (int i = 0; i < length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int a = nums[i];
            int left = i + 1, right = length - 1;
            // 找到当前a的所有符合 a+b+c的情况
            while (left < right) {
                int b = nums[left], c = nums[right];
                if (a + b + c == 0) {
                    List<Integer> temp = new ArrayList();
                    temp.add(a);
                    temp.add(b);
                    temp.add(c);
                    result.add(temp);
                    // 更新 left 和 right
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                } else if (a + b + c > 0) {
                    right--;
                } else {
                    // a+b+c < 0
                    left++;
                }
            }
        }
        return result;
    }

    /*
     * #problem 1 两数之和
     * */
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hash = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            int b = target - a;
            if (hash.containsKey(b)) {
                return new int[]{i, hash.get(b)};
            } else {
                hash.put(a, i);
            }
        }
        return new int[0];
    }

    public int[] towSum1(int[] nums, int target) {
        for (int i = 0; i < nums.length - 1; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }

    /*
     * #problem 141 环形链表
     * */

    // 1. 利用Set
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return true;
            }
            set.add(head);
            head = head.next;
        }
        return false;
    }

    // 2. 快慢指针
    public boolean hasCycle1(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    /*
     * #problem 206. 反转链表
     * */
    // 1. 使用额外空间，头插法
    public ListNode reverseList(ListNode head) {
        ListNode newHead = new ListNode(-1);
        while (head != null) {
            ListNode next = head.next;
            head.next = newHead.next;
            newHead.next = head;
            head = next;
        }
        return newHead.next;
    }

    // 2. 迭代，不使用额外空间
    public ListNode reverseList1(ListNode head) {
        ListNode pre = null, p = head;
        while (p != null) {
            ListNode next = p.next;
            p.next = pre;
            pre = p;
            p = next;
        }
        return pre;
    }

    // 3. 递归
    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode reverserHead = reverseList2(head.next);
        head.next.next = head;
        head.next = null;
        return reverserHead;
    }

    /*
     * #problem 24. 两两交换链表中的节点
     * */

    // 1. 模拟
    public ListNode swapPairs(ListNode head) {
        // 新的链表头节点如何处理
        ListNode newHead = new ListNode();
        ListNode pre = newHead;
        newHead.next = head;
        ListNode p = head;
        while (p != null && p.next != null) {
            ListNode next = p.next;
            p.next = next.next;
            next.next = p;
            pre.next = p;
            p = p.next;
            pre = p;
        }
        return newHead.next;
    }

    // 2.递归
    public ListNode swapPairs1(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = swapPairs1(head.next.next);
        ListNode next = head.next;
        head.next = newHead;
        next.next = head;
        return next;
    }

    /*
     * #problem 142 环形链表2
     * */
    // 1. 利用Set去重
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) {
                return head;
            }
            set.add(head);
            head = head.next;
        }
        return null;
    }

    // 2. 快慢指针
    public ListNode detectCycle1(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode cur = head;
                while (cur != slow) {
                    cur = cur.next;
                    slow = slow.next;
                }
                return cur;
            }
        }
        return null;
    }

    /*
     * #problem 25 K个一组翻转链表
     * */

    /*
     * 1.
     * */
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode newHead = new ListNode();
        newHead.next = head;
        ListNode pre = newHead;
        ListNode p = head;
        while (p != null) {
            ListNode temp = reverseList(p, k);
            if (temp == p) {
                break;
            }
            pre.next = temp;
            pre = p;
            p = p.next;
        }

        return newHead.next;

    }

    // 反转链表
    private ListNode reverseList(ListNode head, int k) {
        ListNode p = head;
        ListNode pre = head;
        int i = 0;
        while (i < k && p != null) {
            pre = pre.next;
            i++;
        }
        // 说明长度不够
        if (i < k) {
            return head;
        }
        // 开始进行反转操作
        for (i = 0; i < k; i++) {
            ListNode next = p.next;
            p.next = pre;
            pre = p;
            p = next;
        }
        return pre;
    }


    /*
     * #problem 26. 删除有序数组中的重复项
     * */
    // 升序数组 重复项是在一起的
    public int removeDuplicates(int[] nums) {
        int i = 0, j = 0;
        int length = nums.length;
        while (i < length) {
            while (i < length - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
            nums[j++] = nums[i++];
        }
        return j;
    }

    public int removeDuplicates1(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int i = 0, j = 1;
        while (j < nums.length) {
            if (nums[i] == nums[j]) {
                nums[++i] = nums[j];
            }
            j++;
        }
        return i + 1;
    }

    /*
     * #problem 189. 轮转数组
     * */

    // 1.额外空间解法
    public void rotate(int[] nums, int k) {
        int length = nums.length;
        int[] temp = new int[length];
        for (int i = 0; i < length; ++i) {
            int index = (i + k) % length;
            temp[index] = nums[i];
        }
        for (int i = 0; i < length; ++i) {
            nums[i] = temp[i];
        }
    }

    // 2. 翻转数组
    // 1 2 3 4 5 6 7  k = 3  - - - - > - - - >
    // 5 6 7 1 2 3 4         - - - > - - - - >
    /*
    * 全体翻转       < - - - < - - - -
    * 前k个进行翻转   - - - > < - - - -
    * 后续的进行翻转  - - - > - - - - >
    * */
    public void rotate1(int[] nums,int k) {
        int length = nums.length;
        if(nums == null || length == 0 || length == 1) {
            return ;
        }
        k = k % length;
        reverse(nums,0,length-1);
        reverse(nums,0,k-1);
        reverse(nums,k,length-1);
    }

    /**
     * 翻转数组
     */
    private void reverse(int[] nums,int start,int end ) {
       while(start < end) {
           int temp = nums[end];
           nums[end] = nums[start];
           nums[start] = temp;
           start++;
           end --;
       }
    }

    /*
    * #problem 21. 合并两个有序链表
    * */
    // 模拟
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while(list1 != null && list2 != null) {
            if(list1.val < list2.val) {
                ListNode next = list1.next;
                list1.next = tail.next;
                tail.next = list1;
                tail = list1;
                list1 = next;
            } else {
                ListNode next = list2.next;
                list2.next = tail.next;
                tail.next = list2;
                tail = list2;
                list2 = next;
            }
        }
        // 下面这一段代码可以直接换成
        /*
        *  tail.next = list1 == null ? list2 : list1;
        * */
        while(list1 != null) {
            ListNode next = list1.next;
            list1.next = tail.next;
            tail.next = list1;
            tail = list1;
            list1 = next;
        }
        while(list2 != null) {
            ListNode next = list2.next;
            list2.next = tail.next;
            tail.next = list2;
            tail = list2;
            list2 = next;
        }
        return newHead.next;
    }

    // 2. 递归
    public ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        if(list1 == null ) {
            return list2;
        } else if(list2 == null ) {
            return list1;
        } else if ( list1.val < list2.val ) {
            ListNode mergeHead = mergeTwoLists1(list1.next,list2);
            list1.next = mergeHead;
            return list1;
        } else {
            ListNode mergeHead = mergeTwoLists1(list1,list2.next);
            list2.next = mergeHead;
            return list2;
        }
    }

    /*
    * #problem 88. 合并两个有序数组
    * */
    // 1. 额外空间 双指针
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index1 = 0 , index2= 0 ;
        int[] temp = new int[m+n];
        int index = 0 ;
        while(index1 < m && index2 < n) {
            if(nums1[index1] < nums2[index2]) {
                temp[index++] = nums1[index1];
                index1++;
            } else {
                temp[index++] = nums2[index2];
                index2++;
            }
        }
        while(index1 < m ) {
            temp[index++] = nums1[index1++];
        }
        while(index2 < n) {
            temp[index++] = nums2[index2++];
        }
        for(int i = 0; i < temp.length ; i++) {
            nums1[i] = temp[i];
        }
    }

    // 2. 原地修改
    public void merge1(int[] nums1, int m, int[] nums2, int n) {
        int index1 = m-1, index2 = n-1;
        int tail = m+n-1;
        int cur = 0;
        while(index1 >= 0 || index2 >=0) {
            if(index1 <0) {
                cur = nums2[index2--];
            } else if(index2 < 0) {
                cur = nums1[index1--];
            } else if( nums1[index1] > nums2[index2]) {
                cur = nums1[index1--];
            } else {
                cur = nums2[index2--];
            }
            nums1[tail--] = cur;
        }
    }

    /*
    * #problem 66 加一
    * */
    // 1. 向后遍历 然后进位
    public int[] plusOne(int[] digits) {
        int length = digits.length;
        // 进位
        int carry = 1;
        for(int i = length-1; i>=0 ; i--) {
            if(carry <=0) {
                break;
            }
            int curVal = digits[i];
            curVal = curVal + carry;
            carry = curVal/10;
            digits[i] = curVal%10;
        }
        // 说明全部都为九，要进位
        if(carry >0) {
            int[] res = new int[digits.length +1];
            res[0] = 1;
            return res;
        }

        return digits;
    }

    // 2. 向前遍历， 找到第一个不为九的数
    public int[] plusOne1(int[] digits) {
        for(int i = digits.length -1 ; i >=0 ; --i) {
            if(digits[i] != 9) {
                ++digits[i];
                // 后面的元素9置为0
                i++;
                for(;i< digits.length;i++) {
                    digits[i] = 0;
                }
                return digits;
            }
        }
        // 数组中所有的元素都为9
        int[] res = new int[digits.length +1];
        res[0] = 1;
        return res;
    }



}